/*
最长增长子序列方法
贪心加二分获取最长序列
根据前驱序列得到正确索引序列
input -> [6,3,4,5,0]
output -> [1,2,3]
*/
function getSequence(arr) {
  const preIndex = new Array(arr.length),
    indexResult = [0];
  let resultLastIndex, left, right, mid;
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      resultLastIndex = indexResult[indexResult.length - 1];
      // 当前项大于最后一项，直接加入结果res
      if (arr[resultLastIndex] < arrI) {
        preIndex[i] = resultLastIndex;
        indexResult.push(i);
        continue;
      }
      // 当前项小于最后一项，二分查找+替换，找到并替换比当前项大的那项
      (left = 0), (right = indexResult.length - 1);
      while (left < right) {
        // 重合就说明找到了 对应的值,时间复杂度O(logn)
        mid = (left + right) >> 1;
        // mid的值比当前项小，所以不包括mid的值
        if (arr[indexResult[mid]] < arrI) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      // 只替换比当前项大的那一项，如果相同、比当前项的还小就不换了
      if (arrI < arr[indexResult[left]]) {
        if (left > 0) {
          preIndex[i] = indexResult[left - 1];
        }
        indexResult[left] = i;
      }
    }
  }
  // 利用前驱节点重新计算result
  let length = indexResult.length; //总长度
  let prev = indexResult[length - 1]; // 最后一项
  while (length-- > 0) {
    // 根据前驱节点一个个向前查找
    indexResult[length] = prev;
    prev = preIndex[prev];
  }
  return indexResult;
}
// getSequence([6,3,4,5,0])
getSequence([3, 1, 4, 1, 5, 9, 2, 6, 5]) // output -> [1,2,4,7]
// getSequence([2, 2, 2, 3, 3, 3, 4, 4])

